Minimum Loss

Posted on 21 May, 2018 in Algorithm

Hello there, In this post, I will try to analyze Minimum Loss problem from HackerRank

Naive Approach

When we first see the question, the first thing that pops our mind is the naive approach. We use for loop 2 times and find the solution. Following code is naive approach implementation.

int minimumLoss(vector<long> price) {
    int minVal = INT_MAX;

    for(int i=0;i<price.size();i++)
        for(int j=i+1;j<price.size();j++)
            if(price[i]-price[j] < minVal && price[i]-price[j] >= 0)
                minVal = price[i]-price[j];

    return minVal;
}

Figure 1: Naive approach

The code in figure one works in O(n^2) because of two loops. It is quite long. We shall have a better solution.

Improved Approach

We first change our structure. We should store both prices and prices' year. Therefore we use a vector of pairs. This part takes O(n). After that, we need to sort our array in reverse order. This part takes O(nlogn). We can use merge sort. We can compare index with index+1 since we have sorted list. Total time takes O(nlogn).

// Complete the minimumLoss function below.
int minimumLoss(vector<long> price) {
    // Creating the nodes with their location in the original array.
    vector<pair<long,int>> priceLoc = {};
    for(int i=0;i<price.size();i++)
        priceLoc.push_back(make_pair(price[i], i));

    // Sorting priceLoc in reverse order.
    sort(priceLoc.begin(),priceLoc.end());
    reverse(priceLoc.begin(), priceLoc.end());

    // Finding the min by using priceLoc array.
    int minVal = INT_MAX;
    for(int i=0;i<priceLoc.size()-1;i++){
        long priceFrst = priceLoc[i].first, priceSec = priceLoc[i+1].first;
        int locOne = priceLoc[i].second, locTwo = priceLoc[i+1].second;
        if(priceFrst-priceSec < minVal && locOne<locTwo)
            minVal = priceLoc[i].first-priceLoc[i+1].first;
    }

    return minVal;
}

Figure 2: The solution

algorithm sorting HackerRank